package 力扣;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yyq
 * @create 2022-02-24 20:07
 */
public class leetcode47 {
    public static void main(String[] args) {
        int[] nums={1,1,2};

    }
    List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used=new boolean[nums.length];
        backTracking(nums,used);
        return lists;
    }

    private void backTracking(int[] nums, boolean[] used) {
        if(list.size()== nums.length){
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i=0;i<nums.length;i++){
            // 剪支
            if(used[i]) continue;
            if(i-1>=0 && nums[i-1]==nums[i]) continue;
            used[i]=true;
            list.add(nums[i]);
            backTracking(nums,used);
            used[i]=false;
            list.remove(list.size()-1);
        }

    }
}
